The present invention relates to the field of telecommunications, and more particularly the routing protocols and network elements that implement such protocols.
A conventional telecommunication network comprises network elements, called routers, the function of which is to optimize the transmission of the packets. In practice, the transmission of a packet from one element to another element in the network can generally be performed along several paths. The routers make it possible to optimize such a transmission by selecting the best transmission path from the possible transmission paths based on certain performance criteria. Such criteria may, for example, correspond to the shortest path in terms of number of hops between two routers, or even the path that maximizes an economic benefit for the operation of the network concerned. A router thus selects a transmission path on the basis of information generally received according to a routing protocol and stored in routing tables.
A routing protocol is a protocol which provides a router with the mechanisms enabling a router to construct such a routing table and to share the routing information with other routers with which it maintains a session according to the routing protocol. There are several types of routing protocols that use different methods to assist the router in collecting routing information and make it possible to determine a routing topology indicating the best routing paths in the network, in light of certain criteria, to reach a given resource from a given router.
The routing topology of a network can be modified, notably when a network router fails. In this case, one or more best routing paths may disappear and other “best paths” are then once again determined according to the routing protocol implemented in the network concerned. The time period during which new best paths are determined corresponds to the “routing protocol convergence” period.
The performance of such a transmission network is strongly dependent on the speed with which the routing topology can converge. In practice, the faster the convergence of the routing topology, the faster the packets are routed over the best paths of the network. Furthermore, during the convergence period of the routing topology, numerous packets may be lost.
FIG. 1 illustrates such a network of routers, comprising five routers N1 to N5, the routers N1, N2 and N5 respectively having resources R1, R2 and R3. In the present context, a resource may be a destination in the network, like an IP address or a set of IP addresses (for example, an IP prefix).
In this context, each router Nj, for j between 1 and 5, selects a best path to contact each resource R1, R2 and R3. In this network, depending on the routing protocol used, the routers Nj exchange information on their capacity to contact the various resources Ri, for i between 1 and 3. The implementation of a routing protocol allows for the exchange of routing information between the various routers so as to update the respective routing tables and thus save the “best” paths.
The routing table of each router indicates the respective best paths for contacting the resources of the network, and all the best paths make up the routing topology of the network. If, upon receipt of update messages from other routers, a new best path is determined to contact a given resource, then this router modifies its routing table and informs the neighboring routers thereof, that is to say, the routers that are linked to it by a direct link according to the routing topology. The term “direct link” should be understood to mean a link that links two routers directly with no other intermediate router.
Then, when a router has determined all its best paths to the various resources of the network, it stops modifying its routing table and therefore sending new update messages according to the routing protocol. The router has then converged in the sense of the routing protocol.
When the routing topology of the network is in a stable state, no update message according to the routing protocol is sent. On convergence of the routing protocol, the best paths between the various routers are illustrated by arrowed lines in FIG. 1.
FIG. 2 complements FIG. 1 by illustrating, in tree form, the best paths for contacting the resources of the network from the routers. Thus, the tree of best paths for contacting the resource R3 is illustrated in a part 31, the tree of best paths for contacting the resource R2 is illustrated in a part 32, and the tree of best paths for contacting the resource R1 is illustrated in a part 33. Here, the criterion used to select the best path corresponds in fact to the shortest path in terms of number of hops.
It should be noted that, for a given resource Ri, the convergence time of the routing protocol, and the number of messages exchanged according to this protocol between the various routers of the network, and the number of transient states through which the network passes during the convergence of the routing protocol, are very strongly linked to the order in which the nodes of the network receive their messages. In practice, the ideal case corresponds to the case in which the first path learned by a router is its best path. In this case, the routing protocol converges rapidly. The worst case corresponds to the case where each router learns, in reverse order of its preferences, the various possible paths for contacting the resource concerned, that is to say, in reverse order of the paths that will be the best paths for it.
As it happens, the performance levels of a network depend on the speed of convergence of the routing protocol used in this network and on the number of messages exchanged according to this protocol between the various routers of the network.
A document entitled “Differentiated BGP update processing for improved routing convergence” by W. Sun, Z. M. Mao and K. G. Shin, May 2006, describes a method of managing exchanges of messages according to the BGP routing protocol.
The management method described here aims, in the case of modification of the routing topology, to broadcast the routing table update messages according to the routing protocol concerned as a priority along best path trees, that is to say, according to the routing topology existing before the modification of the routing topology. Thus, each node of the tree is updated by its parent in the tree existing before the modification of the routing topology. As it happens, its parent in the existing tree may no longer correspond to its parent in the future tree, following the modification of the topology.
Such a method can greatly increase the convergence time of the routing protocol. Furthermore, effectively managing certain routing topology modification situations, such as, notably, the appearance of a new resource in the network, is a complex matter, since there is now no tree for this resource over which to broadcast.